package com.tiny.work.heap;

public class HeapSort {

  public static void main(String[] args) {
    int[] array = {16, 4, 10, 14, 7, 9, 3, 2, 8, 1};
    HeapSort.buildMaxHeap(array, array.length);


    for (int i = array.length - 1; i>=0;i--){
      swap(array, 0, i);
      maxHeapify(array,0, i);
    }

    for (int i = 0; i < array.length; i++) {
      System.out.println(array[i]);
    }
  }

  public static void buildMaxHeap(int[] array, int heapSize) {
    int iParent = (int) Math.floor((heapSize - 1) / 2);
    for (int index = iParent; index >= 0; index--) {
      maxHeapify(array, index, heapSize);
    }
  }

  public static void maxHeapify(int[] array, int index, int heapSize) {
    int iMax, iLeft, iRight;
    while (true) {
      iMax = index;
      iLeft = index * 2 + 1;
      iRight = index * 2 + 2;
      if (iLeft < heapSize && array[iMax] < array[iLeft]) {
        iMax = iLeft;
      }
      if (iRight < heapSize && array[iMax] < array[iRight]) {
        iMax = iRight;
      }
      if (iMax != index) {
        swap(array, iMax, index);
        index = iMax;
      } else {
        break;
      }
    }
  }

  public static void swap(int[] array, int i, int j) {
    int tmp = array[i];
    array[i] = array[j];
    array[j] = tmp;
  }

}
